// https://www.lintcode.com/problem/maximum-subarray/

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        // write your code here
        int ret = -2147483648;
        int i = 0, sum = 0;
        while (i < nums.length) {
            sum += nums[i];
            if (sum > ret) {
                ret = sum;
            }
            if (sum < 0) {
                sum = 0;
            }
            ++i;
        }
        return ret;
    }
}